COMP124

Recursion

A recursive subroutine is one that calls itself
Mutual recursion is where two (or more) subroutines call each other recursively
For example, if sub1 calls sub2, and sub2 calls sub1

Terminating Case

There are two parts to a recursive subroutine

• The general case (the bit that calls itself recursively)
• The terminating case (the bit that causes it to stop)
  Without a terminating case, the code will result in an infinite loop

For example, to computer a factorial of a number:

• The general case is: factorial(N) = N * factorial(N-1)
• The terminating case applies when N is 1: factorial(1) = 1

In assembly, using the accumulator to store the initial parameter:

; SUB factorial
factorial:
	cmp eax, 2
	jl termcase
	push eax
	dec eax
	call factorial
	pop ebx
	mul ebx
	ret
termcase:
	mov eax, 1
	ret
; END factorial

It is always possible to make an iterative version of a recursive algorithm
Sometimes the iterative version will be a lot simpler, usually when the recursive version is tail-recursive
Many problems are easier to conceptualise and solve with recursive algorithms
Recursion implicitly uses the stack (of nested calls and frames) as a data structure to simplify the algorithm, however stack frames take up memory which can be wasteful

Iterative Factorial

Assuming num is the number we want to calculate:

mov eax, 1
mov ecx, num
jecxz finish
floop:
	mul ecx
	loop floop
finish:
	...

The jecxz instruction jumps if ecx is zero
Iterative algorithms use loops and variables instead of nested calls and the stack

Palindrome Checker

A palindrome is a string that reads the same in both directions
Consider the word "rotator"

In terms of recursion:

• The general case is:
  • A) letter at each end matches, and
  • B) letters in between are also a palindrome
• The terminating case applies when:
  • A) string only has one letter, or
  • B) string only has two letters which are the same

Design Decisions

Parameters will be on the stack (string address and length)
Return 0 (false) or 1 (true) in the accumulator

Pop length into ebx and address into eax

Find character at start and end of string, compare them and jump according to the result
If the characters don't match, store 0 in eax and return

If they do match, set up a recursive call:

• Increase eax so it points to the next character along
• Decrease ebx by two so the length is reduced (first and last letter omitted)
• Push those values to the stack
• Make the recursive call
• Return the result

Also, for the terminating case:

• Store 1 in eax and return if there is only one character (or less)

char msg[] = "Hello"; stores as [72, 101, 108, 108, 111, 0] in memory

In ASCII, each character takes up one byte of memory
Strings always use one extra byte to store the string terminator (NUL)
Load the address of the start of the string into a register:
lea eax, msg

Accessing a Single Character in Memory

Each register in a 32-bit system stores 4 bytes of memory
Moving content of string address into a register (mov edx, [eax]) will take the next four bytes and treat it as an integer (which is not what we want)
To get the single byte (character value) instead:

• movzx edx, byte ptr [eax]
  Treats address as pointer to a single byte and zero fills the register

With incoming parameters on the stack, and returning the result in the accumulator:

; SUB palindrome
palindrome:
	pop ebx
	pop eax
	cmp ebx, 1
	jle single ; one or less characters left
	dec ebx
	movzx ecx, byte ptr [eax]
	add eax, ebx
	movzx edx, byte ptr [eax]
	cmp ecx, edx
	jne failure   ; characters dont match
	dec ebx
	sub eax, ebx
	push eax
	push ebx
	call palindrome
	ret
single:
	mov eax, 1
	ret
failure:
	mov eax, 0
	ret
; END palindrome

Length of String

The C library has a function that returns the length of a string
From assembly:

• Push address of string onto stack
• Call the strlen external subroutine
• Result will be stored in the accumulator
• Clean up the stack
  Need to include the C string library code to use this:
• #include <string.h>